Pattern classification (also know as pattern recognition) has received increased attention lately, since it can be used in various applications. For example, face recognition technology, which involves classification of face images, can be used in applications such as surveillance, security, advertising, and the like.
Pattern classification involves classifying data points in an input space where the data points correspond to the images or patterns to be classified. The data points typically lie on a complex manifold in the input space, and pattern classification is carried out by determining how close the data points are to reference data points corresponding to reference images. For example, in face recognition, a face image is typically a two-dimensional N by N array of intensity values and each face image can be represented in the input space as a vector having a dimension N2 in the input space having a dimension N2. A set of face images corresponds to a set of data points (vectors) in the N2 dimensional input space, and the data points typically constitute a complex manifold in the N2 dimensional input space. Face recognition involves determining how close the data points corresponding to the face images are to data points corresponding to reference face images.
In order to determine how close the data points are to each other and to the reference data points in the input space for pattern classification, the nature of the manifold should be taken into consideration. That is, the geodesic distance (distance metrics along the surface of the manifold) between data points in the input space should be used to determine how close the data points are, because the geodesic distance reflects the intrinsic geometry of the underlying manifold.
FIG. 1A is a diagram illustrating an example of a complex manifold 100 on which data points of different classes are displayed in distinct shaded patches, and FIG. 1B is a diagram illustrating data points sampled from these different classes shown in the manifold 100 of FIG. 1A For a pair of points on the manifold 100 in FIG. 1A, their Euclidean distance may not accurately reflect their intrinsic similarity and consequently is not suitable for use in pattern classification. For example, referring to FIG. 1B, the Euclidean distance between two data points (e.g., x1 and x2) may be deceptively small in the three-dimensional input space, although the geodesic distance between the two data points (x1 and x2) on the intrinsic two-dimensional manifold 100 is large. Therefore, the geodesic distance should be used to determine how close the data points (x1 and x2) are on the manifold, since the geodesic distance reflects the intrinsic geometry of the underlying manifold 100.
Recently, the Isomap method (also known as “isometric feature mapping”) and the Locally Linear Embedding (LLE) method have been proposed for learning the intrinsic geometry of complex manifolds using local geometric metrics within a single global coordinate system. The conventional Isomap method first constructs a neighborhood graph that connects each data point on the manifold to all its k-nearest neighbors or to all the data points within some fixed radius ε in the input space. For neighboring points, the input space Euclidean distance usually provides a good approximation of their geodesic distance. For each pair of data points, the shortest path connecting them in the neighborhood graph is computed and is used as an estimate of the true geodesic distance. These estimates are good approximations of the true geodesic distances if there are a sufficient number of data points on the manifold in the input space like FIG. 1B. A conventional multi-dimensional scaling method is then applied to construct a low dimensional subspace that best preserves the manifold's estimated intrinsic geometry.
The Locally Linear Embedding (LLE) method captures local geometric properties of the complex embedding manifolds by a set of linear coefficients in the high dimensional input space that best approximates each data point from its neighbors in the input space. LLE then finds a set of low dimensional points where each point can be linearly approximated by its neighbors with the same set of coefficients that was computed from the high dimensional data points in the input space while minimizing reconstruction cost.
Although the conventional Isomap method and the LLE method have demonstrated acceptable results in finding the embedding manifolds that best describe the data points with minimum reconstruction error as compared to, they fail to represent the images in an optimum way as to facilitate classification of those images. Furthermore, the conventional Isomap method and the LLE method assume that the embedding manifold is well sampled, which may not be the case in some classification problems such as face recognition since there are typically only a few samples available for each person.
Therefore, there is a need for a method of optimally representing patterns such that the classification of such patterns are facilitated and the intrinsic geometry of the underlying manifold of the data points corresponding to the patterns are preserved.